package leetcode_day._2021._202106._2130;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/26 13:56
 * 滑动谜题
 * 算法：BFS
 * 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
 * 所以根据 0 的移动来变换状态
 * 套路跟 752 一样
 * 先把二维数组转化成一个字符串
 * idx = x * 3 + y
 * x = idx / 3, y = idx % 3
 * 记住 0 的位置
 */
public class _26_773 {
    class Node {
        String word; int x, y;
        public Node(String _word, int _x, int _y) {
            word = _word; x = _x; y = _y;
        }
    }
    public int slidingPuzzle(int[][] board) {
        String word = "";
        int x = 0, y = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                word += board[i][j];
                if (0 == board[i][j]) {
                    x = i;
                    y = j;
                }
            }
        }
        if ("123450".equals(word)) return 0;
        Node root = new Node(word, x, y);
        HashSet<String> visited = new LinkedHashSet<>();
        visited.add(word);
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int step = 0;
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            for (int i = 0; i < curSize; i++) {
                Node curNode = queue.poll();
                if (bfs(curNode, visited, queue)) return step + 1;
            }
            ++step;
        }
        return -1;
    }
    int[][] mov = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    boolean bfs(Node curNode, HashSet<String> visited, Queue<Node> queue) {
        char[] array = curNode.word.toCharArray();
        int x = curNode.x, y = curNode.y;
        for (int i = 0; i < mov.length; i++) {
            int newX = x + mov[i][0], newY = y + mov[i][1];
            if (newX < 0 || newX > 1 || newY < 0 || newY > 2) continue;
            int idx1 = x * 3 + y, idx2 = newX * 3 + newY;
            char o1 = array[idx1], o2 = array[idx2];
            array[idx1] = o2;
            array[idx2] = o1;
            String s = new String(array);
            if ("123450".equals(s)) return true;
            if (!visited.contains(s)) {
                queue.offer(new Node(s, newX, newY));
                visited.add(s);
            }
            array[idx1] = o1;
            array[idx2] = o2;
        }
        return false;
    }

}
